import java.util.HashMap;
import java.util.Map;

public class Solution {
    public String minWindow(String s, String t) {
        // 用于记录字符串 t 中每个字符的出现次数
        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        // 用于记录当前滑动窗口内每个字符的出现次数
        Map<Character, Integer> windowMap = new HashMap<>();
        // 记录当前窗口中已经满足要求的字符种类数
        int valid = 0;
        // 滑动窗口的左右边界
        int left = 0, right = 0;
        // 最小窗口的起始位置和长度
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            // 获取当前要加入窗口的字符
            char c = s.charAt(right);
            // 窗口右移
            right++;
            // 如果该字符是 t 中的字符
            if (targetMap.containsKey(c)) {
                // 更新窗口内该字符的出现次数
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
                // 当窗口内该字符的出现次数等于 t 中该字符的出现次数时，满足要求的字符种类数加 1
                if (windowMap.get(c).equals(targetMap.get(c))) {
                    valid++;
                }
            }

            // 判断左侧窗口是否需要收缩
            while (valid == targetMap.size()) {
                // 更新最小窗口的位置和长度
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // 获取要移除窗口的字符
                char d = s.charAt(left);
                // 窗口左移
                left++;
                // 如果该字符是 t 中的字符
                if (targetMap.containsKey(d)) {
                    // 当窗口内该字符的出现次数等于 t 中该字符的出现次数时，满足要求的字符种类数减 1
                    if (windowMap.get(d).equals(targetMap.get(d))) {
                        valid--;
                    }
                    // 更新窗口内该字符的出现次数
                    windowMap.put(d, windowMap.get(d) - 1);
                }
            }
        }
        // 如果最小长度仍为 Integer.MAX_VALUE，说明没有找到符合条件的窗口，返回空字符串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}